package com.test;

import java.util.ArrayList;
import java.util.List;

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}

class Solution {
	public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> ret = new ArrayList<>();
		if (root == null) {
			return ret;
		}
		List<TreeNode> list = new ArrayList<>();
		list.add(root);
		doIt(ret, list);
		return ret;
	}

	public void doIt(List<List<Integer>> ret, List<TreeNode> list) {
		boolean allNull = true;
		List<Integer> dataList = new ArrayList<>();
		for (TreeNode treeNode : list) {
			if (treeNode != null) {
				dataList.add(treeNode.val);
				allNull = false;
			}
		}
		

		if (allNull) {
			return;
		}
		
		ret.add(dataList);

		List<TreeNode> newList = new ArrayList<TreeNode>();
		for (TreeNode treeNode : list) {
			if(treeNode!=null){
				newList.add(treeNode.left);
				newList.add(treeNode.right);
			}
		}
		doIt(ret, newList);
	}

	public int minDepth(TreeNode root) {
		if (root == null)
			return 0;
		if (root.left == null)
			return minDepth(root.right) + 1;
		if (root.right == null)
			return minDepth(root.left) + 1;

		int left = minDepth(root.left) + 1, right = minDepth(root.right) + 1;
		return Math.min(left, right);

	}
}